package leetCode.solution;

import java.util.Deque;
import java.util.LinkedList;

public class Solution32 {
	
	public static void main(String[] args) {
		System.out.println(new Solution32().longestValidParentheses("())(())"));
	}
	
	public int longestValidParentheses2(String s) {
		if(s==null || s.length()<=1) {
			return 0;
		}
		
		char[] arr = s.toCharArray();
		// i位置 左侧连续正确个数
		int [] left = new int[arr.length];
		left[0]=0;
		int result = left[1]=arr[0]=='('&&arr[1]==')'?2:0;
		for(int i = 2;i<left.length;i++) {
			if(arr[i]=='(') {
				left[i]=0;
			}
			if(arr[i]==')') {
				if(i-left[i-1]-1<0 || arr[i-left[i-1]-1]==arr[i]) {
					left[i]=0;
				}else{
					left[i]=left[i-1]+2 + ((i-left[i-1]-2)>=0?left[i-left[i-1]-2]:0);
				}
			}
			result = Math.max(result, left[i]);
		}
		return result;
    }
	
	public int longestValidParentheses(String s) {
        int maxans = 0;
        Deque<Integer> stack = new LinkedList<Integer>();
        stack.push(-1);
        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) == '(') {
                stack.push(i);
            } else {
                stack.pop();
                if (stack.isEmpty()) {
                    stack.push(i);
                } else {
                    maxans = Math.max(maxans, i - stack.peek());
                }
            }
        }
        return maxans;
    }
	
	public int longestValidParentheses3(String s) {
        int left = 0, right = 0, maxlength = 0;
        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) == '(') {
                left++;
            } else {
                right++;
            }
            if (left == right) {
                maxlength = Math.max(maxlength, 2 * right);
            } else if (right > left) {
                left = right = 0;
            }
        }
        left = right = 0;
        for (int i = s.length() - 1; i >= 0; i--) {
            if (s.charAt(i) == '(') {
                left++;
            } else {
                right++;
            }
            if (left == right) {
                maxlength = Math.max(maxlength, 2 * left);
            } else if (left > right) {
                left = right = 0;
            }
        }
        return maxlength;
    }


	// 错误，不连续
	public int longestValidParentheses1(String s) {
		if(s==null || s.length()==1) {
			return 0;
		}
		char[] arr = s.toCharArray();
		int num = 0;
		int result = 0;
		for(int i = 0;i<arr.length;i++) {
			if(arr[i]==')') {
				num-=1;
				result+=1;
			}
			if(num<0) {
				result-=1;
				num=0;
			}
			num=Math.max(num, 0);
			if(arr[i]=='(') {
				num+=1;
			}
		}
		return result*2;
    }
}
